package leetcode.Y2024M6.study;

import leetcode.Y2024M6.TreeNode;

import java.util.*;

/**
 * S173
 */
public class BSTIterator {
    private Deque<TreeNode> stack = new LinkedList<>();

    public BSTIterator(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }

    }


    public int next() {
        TreeNode node = stack.pop();
        if (node.right != null) {
            TreeNode p = node.right;
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
        }
        return node.val;


    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
}
